home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk.zip / HASH.C < prev    next >
C/C++ Source or Header  |  1991-04-07  |  4KB  |  170 lines
  1.  
  2. /********************************************
  3. hash.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the Awk programming language as defined in
  8. Aho, Kernighan and Weinberger, The AWK Programming Language,
  9. Addison-Wesley, 1988.
  10.  
  11. See the accompaning file, LIMITATIONS, for restrictions
  12. regarding modification and redistribution of this
  13. program in source or binary form.
  14. ********************************************/
  15.  
  16.  
  17. /* $Log:    hash.c,v $
  18.  * Revision 2.1  91/04/08  08:23:13  brennan
  19.  * VERSION 0.97
  20.  * 
  21. */
  22.  
  23.  
  24. /* hash.c */
  25.  
  26. #include "mawk.h"
  27. #include "memory.h"
  28. #include "symtype.h"
  29. #include <string.h>
  30.  
  31.  
  32. unsigned hash(s)
  33.   register char *s ;
  34. { register unsigned h = 0 ;
  35.  
  36.   while ( *s )  h += h + *s++ ;
  37.   return  h  ;
  38. }
  39.  
  40. typedef struct hash {
  41. struct hash *link ;
  42. SYMTAB  symtab ;
  43. }  HASHNODE ;
  44.  
  45. static  HASHNODE *PROTO( delete, (char *) ) ;
  46.  
  47. #define  new_HASHNODE() (HASHNODE *) zmalloc(sizeof(HASHNODE))
  48.  
  49. static HASHNODE *hash_table[HASH_PRIME] ;
  50.  
  51. /*
  52.  *   insert -- s is not there and need not be duplicated
  53.  *   -- used during initialization
  54.  */
  55.  
  56. SYMTAB *insert(s) 
  57.   char *s ;
  58. { register HASHNODE *p = new_HASHNODE();
  59.   register unsigned h ;
  60.   
  61.   p->link = hash_table[h = hash(s) % HASH_PRIME ] ;
  62.   p->symtab.name = s ;
  63.   hash_table[h] = p ;
  64.   return &p->symtab ;
  65. }
  66.  
  67. /*
  68.  *  find --  s might be there, find it else insert and dup
  69.  *  s 
  70.  */
  71.  
  72. SYMTAB *find(s)
  73.   char *s ;
  74. { register HASHNODE *p ;
  75.   HASHNODE *q ;
  76.   unsigned h ;
  77.  
  78.   p = hash_table[h = hash(s) % HASH_PRIME ] ;
  79.   q = (HASHNODE *) 0 ;
  80.   while ( 1 )
  81.   { if ( !p )
  82.     { p = new_HASHNODE() ;
  83.       p->symtab.type = ST_NONE ;
  84.       p->symtab.name = strcpy(zmalloc( strlen(s)+1 ), s) ;
  85.       break ;
  86.     }
  87.  
  88.     if ( strcmp(p->symtab.name, s) == 0 ) /* found */
  89.       if ( !q )  /* already at the front */
  90.         return  &p->symtab ;
  91.       else /* delete from the list */
  92.       { q->link = p->link ;  break ; }
  93.  
  94.     q = p ; p = p->link ;
  95.   }
  96.   /* put p on front of the list */
  97.   p->link = hash_table[h] ;
  98.   hash_table[h] = p ;
  99.   return & p->symtab ;
  100. }
  101.  
  102.  
  103. /* remove a node from the hash table
  104.    return a ptr to the node */
  105.  
  106. static unsigned last_hash ;
  107.  
  108. static  HASHNODE  *delete( s )
  109.   char *s ;
  110. { register HASHNODE *p ;
  111.   HASHNODE *q = (HASHNODE *) 0 ;
  112.   unsigned h ;
  113.  
  114.   p = hash_table[ last_hash = h = hash(s) % HASH_PRIME ] ;
  115.   while ( p )
  116.       if ( strcmp(p->symtab.name, s) == 0 )  /* found */
  117.       {
  118.         if ( q )  q->link = p->link ;
  119.         else  hash_table[h] = p->link ;
  120.         return p ;
  121.       }
  122.       else { q = p ; p = p->link ; }
  123.  
  124. #ifdef  DEBUG   /* we should not ever get here */
  125.   bozo("delete") ;
  126. #endif
  127.   return (HASHNODE *) 0 ;
  128. }
  129.  
  130. /* when processing user functions,  global ids which are
  131.    replaced by local ids are saved on this list */
  132.  
  133. static HASHNODE  *save_list ;
  134.  
  135. /* store a global id on the save list,
  136.    return a ptr to the local symtab  */
  137. SYMTAB *save_id( s )
  138.   char *s ;
  139. { HASHNODE *p, *q ;
  140.   unsigned h ;
  141.  
  142.   p = delete(s) ;
  143.   q = new_HASHNODE() ;
  144.   q->symtab.type = ST_LOCAL_NONE ;
  145.   q->symtab.name = p->symtab.name ;
  146.   /* put q in the hash table */
  147.   q->link = hash_table[ h = last_hash ] ;
  148.   hash_table[h] = q ;
  149.  
  150.   /* save p */
  151.   p->link = save_list ; save_list = p ;
  152.  
  153.   return & q->symtab ;
  154. }
  155.  
  156. /* restore all global indentifiers */
  157. void  restore_ids()
  158. { register HASHNODE *p, *q ;
  159.   register unsigned h ;
  160.  
  161.   q = save_list ; save_list = (HASHNODE *) 0 ;
  162.   while ( q )
  163.   {
  164.     p = q ; q = q->link ;
  165.     zfree( delete(p->symtab.name) , sizeof(HASHNODE) ) ;
  166.     p->link = hash_table[h = last_hash ] ; 
  167.     hash_table[h] = p ;
  168.   }
  169. }
  170.